# Python 2.6.4
# Project Euler, Problem 104
# Copyright 2010 Talha Zaman

def fib():
    n1, n2 = 1, 1
    while True:
        yield n1
        n1, n2 = n2, n1+n2

def fib10():
    n1, n2 = 1, 1
    while True:
        yield n1
        n1, n2 = n2, n1+n2%10000000000

def fibtop10():
    n1, n2 = 1, 1
    while True:
        yield n1
        n1, n2 = n2, n1+n2
        drop = str(n1)
        digits = drop.find("0", 15)
        if digits>0 and str(n2)[digits]=="0":
            dropping = len(drop) - digits
            n1 = int(str(n1)[:-dropping])
            n2 = int(str(n2)[:-dropping])

def ispan(n):
    return "123456789".strip(n) == ""

f1, f2, i = fib10(), fibtop10(), 0
while True:
    i = i+1
    a = str(f1.next())
    b = str(f2.next())
    if ispan(a[-9:]) and ispan(b[:9]):
        print i
        break
